package com.zyj.test.month1.day4;

/**
 * @author Yijia Zhang
 * @create 2024-04-26 00:34
 */
public class code0005 {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        int[][] dp = new int[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }
        int max = 1;
        String maxStr = s.substring(0, 1);
        for (int k = 1; k < len; k++) {
            for (int i = 0; i + k < len; i++) {
                int j = i + k;
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 2 || dp[i + 1][j - 1] == 1) {
                        dp[i][j] = 1;
                        if (j - i + 1 > max) {
                            max = j - i + 1;
                            maxStr = s.substring(i, j + 1);
                        }
                    }
                }

            }
        }
        return maxStr;
    }
}
